package company.tree;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 113. 路径总和 II
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 * <p>
 * 叶子节点 是指没有子节点的节点。
 * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
 * 输出：[[5,4,11,2],[5,8,4,5]]
 * <p>
 * 输入：root = [1,2,3], targetSum = 5
 * 输出：[]
 * <p>
 * <p>
 * 输入：root = [1,2], targetSum = 0
 * 输出：[]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/path-sum-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 分析：
 * 1、忽略了节点可以重复，所以不能用map来当前节点的路径
 * 2、所以节点重复的用例过不了，115个用例只过了112
 * 输入：[1,0,1,1,2,0,-1,0,1,-1,0,-1,0,1,0] 2
 * 输出[[1, 0, 1, 0], [1, 0, 2, -1], [1, 1, 0, 0], [1, 1, -1, 1]]
 */
public class PathSum113 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split("\\s+");
        String[] node = input[0].replace("[", "").
                replace("]", "").replace("\\s+", "").split(",");
        input[1].replace("\\s+", "");
        TreeNode treeNode = null;
        treeNode = packTree(treeNode, node);
        System.out.println(pathSum(treeNode, Integer.parseInt(input[1])));
    }

    private static TreeNode packTree(TreeNode treeNode, String[] node) {
        // 根节点
        if (treeNode == null) {
            treeNode = new TreeNode(Integer.parseInt(node[0]));
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(treeNode);
        int idx = 0;
        int len = node.length;
        while (++idx < len) {
            // 取出父节点
            TreeNode poll = deque.poll();

            // 处理左子树
            if (poll.getLeft() == null) {
                if (!node[idx].equals("null")) {
                    TreeNode left = new TreeNode(Integer.parseInt(node[idx]));
                    poll.setLeft(left);
                    deque.offer(left);
                }
            }
            ++idx;

            // 处理右子树
            if (idx < len && poll.getRight() == null) {
                if (!node[idx].equals("null")) {
                    TreeNode right = new TreeNode(Integer.parseInt(node[idx]));
                    poll.setRight(right);
                    deque.offer(right);
                }
            }
        }
        return treeNode;
    }

    private static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> allPath = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        Map<Integer, List<Integer>> map = new HashMap<>();
        List<Integer> path = new ArrayList<>();
        path.add(root.getValue());
        map.put(root.getValue(), path);
        while (!deque.isEmpty()) {
            int cnt = deque.size();
            for (int i = 0; i < cnt; i++) {
                TreeNode poll = deque.poll();
                int parentId = poll.getValue();

                // 取出父节点位置的路径
                List<Integer> paths = map.get(parentId);
                TreeNode left = poll.getLeft();
                TreeNode right = poll.getRight();
                if (left != null) {
                    paths.add(left.getValue());
                    map.put(left.getValue(), new ArrayList<>(paths));
                    deque.offer(left);
                    paths.remove(paths.size()-1);
                }

                if (right != null) {
                    paths.add(right.getValue());
                    map.put(right.getValue(), new ArrayList<>(paths));
                    deque.offer(right);
                    paths.remove(paths.size()-1);
                }
                if (left== null && right==null) {
                    int sum = paths.stream().mapToInt(Integer::intValue).sum();
                    if (sum == targetSum) {
                        allPath.add(new ArrayList<>(paths));
                    }
                }
            }
        }
        return allPath.stream().distinct().collect(Collectors.toList());
    }
}